package com.example.leetcode.trainingcamp.week9.sunday;


/**
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 *
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/word-search
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test79 {

    public boolean[][] visit;

    int width;

    int length;

    boolean is = false;

    public boolean exist(char[][] board, String word) {
        length = board.length;
        width = board[0].length;
        visit = new boolean[length][width];
        int[][] t = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int i = 0;i<length;i++) {
            for (int j = 0 ;j<width;j++){
                if (board[i][j] == word.charAt(0)){
                    visit[i][j] = true;
                    dfs(board,t,word,1,i,j);
                    visit[i][j] = false;
                //    visit = new boolean[length][width];
                }
            }
        }
        return is;
    }


    public void dfs(char[][] board,int[][] t,String word,int count,int r,int c){
        if (count == word.length()) {
            is = true;
            return;
        }
        for (int[] t1:t) {
            int newR = r + t1[0];
            int colR = c + t1[1];
            if ( newR>=0 &&newR<length && colR>=0 && colR<width && !visit[newR][colR] ){
                if (board[newR][colR] == word.charAt(count)){
                    visit[newR][colR] = true;
                    dfs(board,t,word,count+1,newR,colR);
                    visit[newR][colR] = false;
                }
            }
        }
    }
}


class Demo79{
    public static void main(String[] args) {
       // char[][] board = {{'A','B','C','E'},{'S','F','E','S'},{'A','D','E','E'}};
        char[][] board =  {{'C','A','A'},{'A','A','A'},{'B','C','D'}};
        Test79 t = new Test79();
     //   String word = "ABCESEEEFS";
        String word = "AAB";
        boolean exist = t.exist(board, word);
        System.out.println(exist);
    }
}